package Math;

public class _204_CountPrimes {
    //method 1: iterator from 1 to i,check if i%j==0;
    //method 2: sqrt(i), decrease the calculation.
    //method 3: use extra memory,record the not prime number.
    public int countPrimes(int n) {
        boolean[] notprime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!notprime[i]) {
                count++;
                for (int j = 2; i * j < n; j++) {
                    notprime[i*j] = true;
                }
            }
        }
        return count;
    }
}
